


		BLOCAJE - SOLUTIE
	       -------------------

	Avand 2 noduri s si t ale grafului, pt. a le deconecta trebuie sa inlaturam un numar
minim de muchii care este egal cu numarul maxim de drumuri disjuncte (ca muchii) dintre s si t
( teorema este asemanatoare cu teorema lui Menger, demonstratia fiind similara daca se foloses-
te teorema flux maxim/taietura de capacitate minima: "Intr-o retea de transport taietura minima
este egala cu fluxul maxim.").
	Pt. detemrinarea nr. de drumuri disjuncte (ca muchii) dintre s si t, se foloseste algo-
ritmul Edmonds-Karp, aplicat pe o retea de transport, obtinuta prin inlocuirea fiecarei muchii
a grafului initial printr-o pereche de arce simetrice, fiecare din aceste arce avand capacitatea
1. Un flux de valoare maxima, definit pe aceasta retea, reprezinta numarul maxim de drumrui dis-
juncte (ca muchii) dintre s si t. Aparent, ar trebui sa aplicam algoritmul pt. flux maxim pentru
oricare 2 noduri i si j ale grafului si sa alegem valoarea minima dintre toate valorile obtinute
pt. fluxul maxim. De fapt, este suficienta aplicarea algoritmului Edmonds-Karp de n-1 ori pt. re-
teaua de transport avand intrarea s un nod oarecare (fixat) iar iesirea (t) fiind orice nod din
reteaua de transport diferit de s. Acest lucru este dovedit de faptul ca, inlaturand oricare mu-
chii care indeplinesc conditia din enunt (ca deconecteaza cel putin 2 varfuri) va fi deconectata
intrarea s de cel putin un varf care, la un moment dat va fi iesire pentru algoritmul de deter-
minare a fluxului maxim.
	Muchiile care trebuie inlaturate reprezinta o taietura de valoare minima in reteaua pt.
care s-a obtinut valoarea minima a fluxului maxim.

COMPLEXITATE: O(m^2 * n^2).